{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Covered Intervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeCoveredIntervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除被覆盖区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。</p>\n",
    "\n",
    "<p>只有当&nbsp;<code>c &lt;= a</code>&nbsp;且&nbsp;<code>b &lt;= d</code>&nbsp;时，我们才认为区间&nbsp;<code>[a,b)</code> 被区间&nbsp;<code>[c,d)</code> 覆盖。</p>\n",
    "\n",
    "<p>在完成所有删除操作后，请你返回列表中剩余区间的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,4],[3,6],[2,8]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong>​​​​​​</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= intervals.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= intervals[i][0] &lt;&nbsp;intervals[i][1] &lt;= 10^5</code></li>\n",
    "\t<li>对于所有的&nbsp;<code>i != j</code>：<code>intervals[i] != intervals[j]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-covered-intervals](https://leetcode.cn/problems/remove-covered-intervals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-covered-intervals](https://leetcode.cn/problems/remove-covered-intervals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4],[3,6],[2,8]]', '[[1,4],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        count = 0\n",
    "        for i in range(n):#判断i是不是 是就count+=1\n",
    "            for j in range(n):#判断j能不能盖住i\n",
    "                if i==j: continue\n",
    "                if intervals[i][0]>=intervals[j][0] and intervals[j][1]>=intervals[i][1]:\n",
    "                    count+=1\n",
    "                    break\n",
    "        return n-count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        def quick(nums, left, right):\n",
    "            pivot = nums[left]\n",
    "            low,high = left, right\n",
    "            while low<high:\n",
    "                while low<high and (nums[high][0]>pivot[0] or (nums[high][0]==pivot[0] and nums[high][1]<=pivot[1])):\n",
    "                    high -= 1\n",
    "                nums[low] = nums[high]\n",
    "                while low<high and (nums[low][0]<pivot[0] or (nums[low][0]==pivot[0] and nums[low][1]>=pivot[1])):\n",
    "                    low += 1\n",
    "                nums[high] = nums[low]\n",
    "            nums[low] = pivot\n",
    "            return low\n",
    "        def quicksort(nums, left, right):\n",
    "            if left>=right:\n",
    "                return\n",
    "            mid = quick(nums,left,right)\n",
    "            quicksort(nums,left,mid-1)\n",
    "            quicksort(nums,mid+1,right)\n",
    "        quicksort(intervals, 0, len(intervals)-1)\n",
    "        #intervals.sort(key = lambda x:(x[0],-x[1]))\n",
    "        start,end = intervals[0]\n",
    "        cnt = 0\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][1]<=end:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                end = intervals[i][1]\n",
    "        return len(intervals)-cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        i = 1\n",
    "        while i < len(intervals):\n",
    "            if intervals[i][0]>=intervals[i-1][0] and intervals[i][1]<= intervals[i-1][1]:\n",
    "                del intervals[i]\n",
    "            elif intervals[i][0]==intervals[i-1][0] and intervals[i][1] >= intervals[i-1][1]:\n",
    "                del intervals[i-1]\n",
    "            else:\n",
    "                i += 1\n",
    "        return len(intervals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        \n",
    "        n =len(intervals)\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and intervals[j][0]<=intervals[i][0] and intervals[i][1]<=intervals[j][1]:\n",
    "                    ans-=1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        cnt = 0\n",
    "        #pre_begin = 0\n",
    "        pre_end = 0\n",
    "        for i in intervals:\n",
    "            #begin = i[0]\n",
    "            end = i[1]\n",
    "            if pre_end < end:\n",
    "                cnt += 1\n",
    "                pre_end = end\n",
    "\n",
    "\n",
    "        #print(intervals)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        a = intervals\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and a[j][0] <= a[i][0] and a[i][1] <= a[j][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def removeCoveredIntervals(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        res = 1\n",
    "        i=1\n",
    "        while i<n:\n",
    "            if intervals[i][0] == intervals[i-1][0]:\n",
    "                intervals.remove(intervals[i-1])\n",
    "                n-=1\n",
    "            elif  intervals[i][1] <= intervals[i-1][1]:\n",
    "                intervals.remove(intervals[i])\n",
    "                n-=1\n",
    "            elif intervals[i][1] > intervals[i-1][1]:\n",
    "                res+=1\n",
    "                i+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda u: (u[0], -u[1]))\n",
    "        res , rmax = n, intervals[0][1]\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= rmax:\n",
    "                res -= 1\n",
    "            else:\n",
    "                rmax = max(rmax, intervals[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        max_end = -1\n",
    "        pre = None\n",
    "        intervals.sort()\n",
    "        for item in intervals:\n",
    "            if item[1] <= max_end:\n",
    "                continue\n",
    "            max_end = max(max_end, item[1])\n",
    "            if pre and item[0] == pre[0]:\n",
    "                continue\n",
    "            result += 1\n",
    "            pre = item\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        ans = n\n",
    "        for i, (l, r) in enumerate(intervals):\n",
    "            for j in range(n):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                if intervals[j][0] <= l and r <= intervals[j][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "\n",
    "        intervals = sorted(intervals,key=lambda x:(x[0],-x[1]))\n",
    "\n",
    "        result = 0\n",
    "        pre_x = -1\n",
    "        pre_y = -1\n",
    "        for x,y in intervals:\n",
    "            if y<=pre_y:\n",
    "                continue\n",
    "            pre_x=x \n",
    "            pre_y=y \n",
    "            result+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n=len(intervals)\n",
    "        ans=n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and intervals[j][0]<=intervals[i][0] and intervals[i][1]<=intervals[j][1]:\n",
    "                    ans-=1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "       # print(intervals)\n",
    "        last = intervals[0]\n",
    "        lasti = 0\n",
    "\n",
    "        deleted = []\n",
    "\n",
    "        for (i,interval) in enumerate(intervals):\n",
    "            if (i==0):\n",
    "                continue\n",
    "            \n",
    "            a1,b1 = last\n",
    "            a2,b2 = interval\n",
    "            lasti;i;\n",
    "            if (b1>=b2):\n",
    "                deleted.append(i)\n",
    "            elif (a1==a2 and b2>=b1):\n",
    "                deleted.append(lasti)\n",
    "                last = interval\n",
    "                lasti = i\n",
    "            else:\n",
    "                lasti = i\n",
    "                last = interval\n",
    "        # res = []\n",
    "        # for (i,ele) in enumerate(intervals):\n",
    "        #     if (i not in deleted):\n",
    "        #         res.append(ele)\n",
    "            \n",
    "        return len(intervals) - len(deleted)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda sl:(sl[0],sl[1]))\n",
    "        n =  len(intervals)\n",
    "        count = n\n",
    "        pre1 = intervals[0][0]\n",
    "        pre2 = intervals[0][1]\n",
    "        for i in range(1,n): \n",
    "            if pre2 >= intervals[i][1]:  # 右边界>= 前一个数的右边界，递增那么肯定是覆盖了  \n",
    "                count -= 1\n",
    "            else: # 当前区间右边界比上一个大，区分到底是 相交 还是 覆盖\n",
    "                    # 更新边界\n",
    "                if pre1 == intervals[i][0]:  # 说明是覆盖了\n",
    "                    count -= 1\n",
    "                else: # 相交了\n",
    "                    pre1 = intervals[i][0]\n",
    "                pre2 = intervals[i][1]         \n",
    "\n",
    "        return  count               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        res=[intervals[0]]\n",
    "        for c in intervals:\n",
    "            if res[-1][1]>=c[1]:continue\n",
    "            elif res[-1][0]==c[0] and res[-1][1]<=c[1]:res[-1]=c\n",
    "            else:res.append(c)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        right = []\n",
    "        ans = len(intervals)\n",
    "        for intl in intervals:\n",
    "            if not right or intl[1] > right[-1][1]:\n",
    "                if right and intl[0] == right[-1][0]:\n",
    "                    right.pop()\n",
    "                    ans -= 1\n",
    "                right.append(intl)\n",
    "            else:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        length = len(intervals)\n",
    "        for i in range(len(intervals)):\n",
    "            for j in range(len(intervals)):\n",
    "                if intervals[i][0] >= intervals[j][0] and intervals[i][1] <= intervals[j][1] and i != j:\n",
    "                    length -= 1\n",
    "                    break\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        def check(j):\n",
    "            for i in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if intervals[i][0] <= intervals[j][0] and intervals[j][1] <= intervals[i][1]:\n",
    "                    return True\n",
    "            return False\n",
    "        return len([i for i in range(n) if not check(i)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        oringin = intervals[:]\n",
    "        for i in oringin:\n",
    "            copy = intervals[:]\n",
    "            copy.remove(i)\n",
    "            for j in copy:\n",
    "                # print(i,j)\n",
    "                if i[0] >= j[0] and i[1] <= j[1]:\n",
    "                    # print(i)\n",
    "                    intervals.remove(i)\n",
    "                    break\n",
    "        # print(intervals)\n",
    "        count = 0\n",
    "        for _ in intervals:\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda u: (u[0], -u[1]))\n",
    "        ans, rmax = n, intervals[0][1]\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= rmax:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                rmax = max(rmax, intervals[i][1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):  # 肯定是后面的数\n",
    "                if i != j and intervals[j][0] <= intervals[i][0] and intervals[j][1] >= intervals[i][1]:\n",
    "                    count += 1\n",
    "                    break\n",
    "        return n - count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        #intervals = sorted(intervals, key = lambda x: (x[0], -x[1]))\n",
    "        intervals.sort(key = lambda x: (x[0], -x[1]))\n",
    "        left = intervals[0][0]\n",
    "        right = intervals[0][1]\n",
    "        res = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            intv = intervals[i]\n",
    "            if left <= intv[0] and right >= intv[1]:\n",
    "                res += 1\n",
    "            if left < intv[0] and right < intv[1]:\n",
    "                right = intv[1]\n",
    "            if right < intv[0]:\n",
    "                left, right = intv[0], intv[1]\n",
    "        return len(intervals) - res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda a: (a[0], -a[1]))\n",
    "\n",
    "        left = intervals[0][0]\n",
    "        right = intervals[0][1]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            intv = intervals[i]\n",
    "            # 区间覆盖\n",
    "            if left <= intv[0] and right >= intv[1]:\n",
    "                res += 1\n",
    "            # 区间相交，合并\n",
    "            if intv[0] <= right <= intv[1]:\n",
    "                right = intv[1]\n",
    "            # 区间完全不相交\n",
    "            if right < intv[0]:\n",
    "                left = intv[0]\n",
    "                right = intv[1]\n",
    "\n",
    "        return len(intervals) - res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        # 先排序\n",
    "        intervals.sort(key = lambda x : (x[0], -x[1]))\n",
    "\n",
    "        # 贪心删除\n",
    "        base = intervals[0]\n",
    "        ans = len(intervals)\n",
    "        for i in range(1, len(intervals)):\n",
    "            if base[0] <= intervals[i][0] and intervals[i][1] <= base[1]:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                base = intervals[i]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda p: [p[0], -p[1]])\n",
    "        r_max = intervals[0][1]\n",
    "        n = len(intervals)\n",
    "        to_del = []\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= r_max:\n",
    "                to_del.append(i)\n",
    "            else:\n",
    "                r_max = max(r_max, intervals[i][1])\n",
    "        return n - len(to_del)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        self.intervals = sorted(intervals,key=lambda u: (u[0], -u[1]))\n",
    "        #print(self.intervals)\n",
    "        res,rmax = len(self.intervals),self.intervals[0][1]\n",
    "        #print(rmax)\n",
    "        for i in range(1,len(self.intervals)):\n",
    "            if self.intervals[i][1]<=rmax:\n",
    "                res-=1\n",
    "            else:\n",
    "                rmax = max(rmax, self.intervals[i][1])\n",
    "                #print(rmax)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda sl:(sl[0],-sl[1]))\n",
    "        n = len(intervals)\n",
    "        count = 0\n",
    "        pre = intervals[0][1]   \n",
    "        for i in range(1,n):\n",
    "            if pre >= intervals[i][1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                pre = max(pre,intervals[i][1])\n",
    "        return n - count           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        '''\n",
    "        n = len(intervals)\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans\n",
    "        '''\n",
    "        n = len(intervals)\n",
    "        removed = n\n",
    "        for i in range(0,n):\n",
    "            for j in range(0,n):\n",
    "                if intervals[j][0] <= intervals[i][0] and intervals[j][1] >= intervals[i][1] and i != j:\n",
    "                    removed -= 1\n",
    "                    #intervals.remove(itvl)\n",
    "                    break\n",
    "        return removed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0],-x[1]))\n",
    "        maxval=-1\n",
    "        res=[]\n",
    "        for i in intervals:\n",
    "            if i[1]>maxval:\n",
    "                res.append(i)\n",
    "            maxval=max(maxval,i[1])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        # 易错点一：引用方式list.sort()\n",
    "        intervals.sort(key=lambda u: (u[0], -u[1]))  # 易错点二：右区间降序排序\n",
    "        res, rmax = n, intervals[0][1]\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= rmax:\n",
    "                res -= 1\n",
    "            else:\n",
    "                rmax = intervals[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda a: (a[0], -a[1]))\n",
    "\n",
    "        result = 0\n",
    "        left, right = intervals[0][0], intervals[0][1]\n",
    "\n",
    "        for i in range(1, len(intervals)):\n",
    "            current = intervals[i]\n",
    "\n",
    "            #fully overlap\n",
    "            if left<=current[0] and right>=current[1]:\n",
    "                result += 1\n",
    "            #not fully overlap\n",
    "            if right>=current[0] and right<=current[1]:\n",
    "                right = current[1]\n",
    "            #not touch\n",
    "            if right<=current[0]:\n",
    "                left, right = current[0], current[1]\n",
    "        \n",
    "        return len(intervals)-result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key= lambda x:(x[0], -x[1]))\n",
    "        res = [intervals[0]]\n",
    "        for i in range(1, len(intervals)):\n",
    "            if res[-1][0] <= intervals[i][0] and res[-1][1] >= intervals[i][1]:\n",
    "                continue\n",
    "            else:\n",
    "                res.append((intervals[i]))\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0], -x[1]))\n",
    "\n",
    "        left, right = intervals[0]\n",
    "\n",
    "        res = 0\n",
    "        for start, end in intervals[1:]:\n",
    "            if left <= start and end <= right:\n",
    "                res += 1\n",
    "            elif left <= start and end > right:\n",
    "                right = end\n",
    "            elif start > end:\n",
    "                left = start\n",
    "                right = end\n",
    "\n",
    "        return len(intervals) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0], -x[1]))\n",
    "        result = [intervals[0]]\n",
    "        for i in range(1, len(intervals)):\n",
    "            if result[-1][0]<=intervals[i][0] and result[-1][1]>=intervals[i][1]:\n",
    "                continue\n",
    "            else:\n",
    "                result.append(intervals[i])\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0],-x[1]))\n",
    "        n=len(intervals)\n",
    "        prer=intervals[0][1]\n",
    "        for i in intervals[1:]:\n",
    "            if i[1]<=prer:\n",
    "                n-=1\n",
    "            else:\n",
    "                prer=i[1]\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1],reverse=True)\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        rt_max = -1\n",
    "        ans = len(intervals)\n",
    "        for seq in intervals:\n",
    "            if seq[1] <= rt_max:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                rt_max = seq[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0], -x[1]))\n",
    "        n = len(intervals)\n",
    "        ans = n\n",
    "        right = intervals[0][1]\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= right:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                right = intervals[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        \n",
    "        intervals.sort(key = lambda u: (u[0], -u[1]))\n",
    "        ans, rmax = n, intervals[0][1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= rmax:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                rmax = intervals[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and intervals[j][0] <= intervals[i][0] and intervals[j][1] >= intervals[i][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda u: (u[0], -u[1]))\n",
    "        ans, rmax = n, intervals[0][1]\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= rmax:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                rmax = max(rmax, intervals[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        ret=1\n",
    "        intervals.sort(key=lambda x:(x[0],-x[1]))\n",
    "        end=intervals[0][1]\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][1]>end:\n",
    "                ret+=1\n",
    "                end=intervals[i][1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n=len(intervals)\n",
    "        intervals.sort(key=lambda x:(x[0],-x[1]))\n",
    "        ans=n\n",
    "        flag=intervals[0][1]\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][1]<=flag:\n",
    "                ans-=1\n",
    "            \n",
    "            flag=max(intervals[i][1],flag)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals = sorted(intervals, key = lambda x: (x[0], -x[1]))\n",
    "        print(intervals)\n",
    "        left = intervals[0][0]\n",
    "        right = intervals[0][1]\n",
    "        res = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            intv = intervals[i]\n",
    "            if left <= intv[0] and right >= intv[1]:\n",
    "                res += 1\n",
    "            if left <= intv[0] and right < intv[1]:\n",
    "                right = intv[1]\n",
    "            if right < intv[0]:\n",
    "                left, right = intv[0], intv[1]\n",
    "        return len(intervals) - res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda u: (u[0], -u[1]))\n",
    "        ans, max_val = len(a), a[0][1]\n",
    "        for i in range(1, len(a)):\n",
    "            if a[i][1] <= max_val:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                max_val = a[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals=sorted(intervals,key=lambda x:(x[0],-x[1]))\n",
    "\n",
    "        #print(intervals)\n",
    "\n",
    "        cur=0\n",
    "        visited=[1 for i in range(len(intervals))]\n",
    "\n",
    "        while(cur<len(intervals)):\n",
    "            \n",
    "            if(visited[cur]==1 and cur+1<len(intervals)):\n",
    "                begin_cur=intervals[cur][0]\n",
    "                end_cur=intervals[cur][1]\n",
    "                next_=cur+1\n",
    "                while(next_<len(intervals)):\n",
    "                    next_begin=intervals[next_][0]\n",
    "                    next_end=intervals[next_][1]\n",
    "\n",
    "                    if(begin_cur<=next_begin and next_end<=end_cur):\n",
    "                        visited[next_]=0\n",
    "                    if(begin_cur>next_end):\n",
    "                        break\n",
    "                    next_+=1\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "            cur+=1\n",
    "\n",
    "        # ans=[]\n",
    "        # for i in range(len(intervals)):\n",
    "        #     if(visited[i]):\n",
    "        #         ans.append(intervals[i])\n",
    "       #print(ans)\n",
    "        return sum(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key = lambda x:(x[0],-x[1]))\n",
    "        ans, rmax = n ,intervals[0][1]\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1]<=rmax:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                rmax = max(rmax, intervals[i][1])\n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0],-x[1]))\n",
    "        left,right=intervals[0][0],intervals[0][1]\n",
    "        res=0\n",
    "        for i in range(1,len(intervals)):\n",
    "            if left<=intervals[i][0] and right>=intervals[i][1]:\n",
    "                res+=1\n",
    "            elif right>intervals[i][0] and right<intervals[i][1]:\n",
    "                right=intervals[i][1]\n",
    "            elif right<intervals[i][0]:\n",
    "                left=intervals[i][0]\n",
    "                right=intervals[i][1]\n",
    "        return len(intervals)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals) == 1:\n",
    "            return 1\n",
    "\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda x : (x[0],-x[1])) # 第一个并不是一定不会不覆盖\n",
    "\n",
    "        max_right = intervals[0][1]\n",
    "        count = 0\n",
    "        for i in range(1, n):\n",
    "            cur_left = intervals[i][0]\n",
    "            cur_right = intervals[i][1]\n",
    "            if cur_right <= max_right:\n",
    "                count += 1\n",
    "            if cur_right > max_right:\n",
    "                max_right = cur_right\n",
    "            \n",
    "        return n - count\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x: (x[0], -x[1]))\n",
    "        stack = []\n",
    "        stack.append(intervals[0])\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][1]>stack[-1][1]:\n",
    "                stack.append(intervals[i])\n",
    "        return len(stack)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x: (x[0], -x[1]))\n",
    "        left, right = intervals[0][0], intervals[0][1]\n",
    "        \n",
    "        n = len(intervals)\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            inter = intervals[i]\n",
    "            if left <= inter[0] and right >= inter[1]:\n",
    "                res += 1\n",
    "            if right >= inter[0] and right <= inter[1]:\n",
    "                right = inter[1]\n",
    "            if right < inter[0]:\n",
    "                left, right = inter[0], inter[1]\n",
    "        return n - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if len(intervals) == 1:\n",
    "            return 1\n",
    "        intervals.sort(key=lambda x:(x[0], -x[1]))\n",
    "        l = intervals[0][0]\n",
    "        r = intervals[0][1]\n",
    "        to_delete = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0]<=r:\n",
    "                if intervals[i][1] <= r:\n",
    "                    to_delete += 1\n",
    "                else:\n",
    "                    r = intervals[i][1]\n",
    "            else:\n",
    "                l = intervals[i][0]\n",
    "                r = intervals[i][1]\n",
    "        return len(intervals)-to_delete"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0], -x[1]))\n",
    "\n",
    "        left, right = intervals[0]\n",
    "\n",
    "        res = 0\n",
    "        for start, end in intervals[1:]:\n",
    "            if left <= start and end <= right:\n",
    "                res += 1\n",
    "            else:\n",
    "                left = start\n",
    "                right = end\n",
    "\n",
    "        return len(intervals) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0], -x[1]))\n",
    "        剩余区间数 = 0\n",
    "        区间上限 = 0\n",
    "        for _, j in intervals:\n",
    "            if j > 区间上限:\n",
    "                剩余区间数 += 1\n",
    "                区间上限 = j\n",
    "        return 剩余区间数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        # 按起点升序，终点降序排序\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        \n",
    "        count = 0\n",
    "        prev_end = 0\n",
    "        \n",
    "        for _, end in intervals:\n",
    "            # 如果当前区间的终点大于前一个区间的终点，\n",
    "            # 则它不能被前一个区间所覆盖\n",
    "            if end > prev_end:\n",
    "                count += 1\n",
    "                prev_end = end\n",
    "                \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda c:(c[0], -c[1]))\n",
    "        maxl = -1\n",
    "        ans = 0\n",
    "        for i in intervals:\n",
    "            if i[1] > maxl:\n",
    "                maxl = i[1]\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        to_del = set()\n",
    "        intervals.sort(key=lambda p: p[1] - p[0], reverse=True)\n",
    "        n = len(intervals)\n",
    "\n",
    "        def f(a, b):\n",
    "            if a[0] <= b[0] and a[1] >= b[1]:\n",
    "                return True \n",
    "            return False\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if i in to_del:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if j in to_del:\n",
    "                    continue\n",
    "                pre, aft = intervals[i], intervals[j]\n",
    "                if f(pre, aft):\n",
    "                    to_del.add(j)\n",
    "        return n - len(to_del)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        # 按照起点升序排列 起点相同时降序排列 \n",
    "        intervals.sort(key=lambda x:(x[0],-x[1]))\n",
    "        # 记录合并区间的起点和终点 \n",
    "        left = intervals[0][0] \n",
    "        right = intervals[0][1]\n",
    "        res = 0\n",
    "        for i in range(1, len(intervals)):\n",
    "            intv = intervals[i]\n",
    "            # 情况一 找到覆盖区间\n",
    "            if left <= intv[0] and right >= intv[1]:\n",
    "                res += 1\n",
    "            # 情况二 找到相交区间 合并\n",
    "            if right >= intv[0] and right <= intv[1]:\n",
    "                right = intv[1]\n",
    "            # 情况三 完全不相交 更新起点和终点 \n",
    "            if right < intv[0]:\n",
    "                left = intv[0]\n",
    "                right = intv[1]\n",
    "        return len(intervals)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[1], -x[0]))\n",
    "    \n",
    "        s = []\n",
    "        for a in intervals:\n",
    "            while s and s[-1][0] >= a[0]:\n",
    "                # a区间覆盖s[-1],栈顶弹出\n",
    "                s.pop()\n",
    "            s.append(a)\n",
    "        \n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals: return 0\n",
    "        intervals.sort(key = lambda x: (x[0], -x[1]))\n",
    "\n",
    "        left = intervals[0][0]\n",
    "        right = intervals[0][1]\n",
    "        res = 1\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] >= left and intervals[i][1] <= right:\n",
    "                continue\n",
    "            else:\n",
    "                res += 1\n",
    "                left = intervals[i][0]\n",
    "                right = intervals[i][1]\n",
    "\n",
    "        return res\n",
    "\n",
    "# 作者：zhsama\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        new_list = [intervals[0]]\n",
    "        for i in range(1, n):\n",
    "            if new_list[-1][1] < intervals[i][1]:\n",
    "                new_list.append(intervals[i])\n",
    "        return len(new_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda u: (u[0], -u[1]))\n",
    "        ans = n\n",
    "        rmax = intervals[0][1]\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= rmax:\n",
    "                ans -= 1\n",
    "            else:\n",
    "                rmax = intervals[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals = sorted(intervals, key = lambda x:(x[0], -x[1]))\n",
    "        \n",
    "        ret = 1\n",
    "        cur_max = intervals[0][1]\n",
    "\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][1] > cur_max:\n",
    "                cur_max = intervals[i][1]\n",
    "                ret += 1\n",
    "        \n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[0], -x[1]))\n",
    "\n",
    "        n = len(intervals)\n",
    "\n",
    "        res = n\n",
    "        l,r = intervals[0][0],intervals[0][1]\n",
    "        for i in range(1,n):\n",
    "            if l <= intervals[i][0] and r >= intervals[i][1]:\n",
    "                res -=1\n",
    "            elif r >= intervals[i][0] and r < intervals[i][1]:\n",
    "                r = intervals[i][1]\n",
    "            elif r < intervals[i][0]:\n",
    "                l = intervals[i][0]\n",
    "                r = intervals[i][1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "            intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "            # 记录合并区间的起点和终点\n",
    "            left, right = intervals[0][0], intervals[0][1]\n",
    "            \n",
    "            res = 0\n",
    "            for i in range(1, len(intervals)):\n",
    "                interval = intervals[i]\n",
    "                # 情况一，找到覆盖区间\n",
    "                if left <= interval[0] and right >= interval[1]:\n",
    "                    res += 1\n",
    "                # 情况二，找到相交区间，合并\n",
    "                if right >= interval[0] and right <= interval[1]:\n",
    "                    right = interval[1]\n",
    "                # 情况三，完全不相交，更新起点和终点\n",
    "                if right < interval[0]:\n",
    "                    left, right = interval[0], interval[1]\n",
    "            \n",
    "            return len(intervals) - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x: (x[0], -x[1]))\n",
    "        max_right = intervals[0][1]\n",
    "        n = len(intervals)\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][1] <= max_right:\n",
    "                res += 1\n",
    "            else:\n",
    "                max_right = intervals[i][1]\n",
    "        return n - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key = lambda x:(x[0], -x[1]))\n",
    "        n = len(intervals)\n",
    "        le, ri = intervals[0][0], intervals[0][1]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if intervals[i][0] >= le and intervals[i][1] <= ri:\n",
    "                res += 1\n",
    "            elif intervals[i][0] <= ri and intervals[i][1] > ri:\n",
    "                ri = intervals[i][1]\n",
    "            elif intervals[i][0] > ri:\n",
    "                le, ri = intervals[i][0], intervals[i][1]\n",
    "        return n - res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\r\n",
    "        intervals.sort(key=lambda x : (x[0], -x[1]))\r\n",
    "        left, right = intervals[0][0], intervals[0][1]\r\n",
    "        res = 0\r\n",
    "        for interval in intervals[1:]:\r\n",
    "            if left <= interval[0] and right >= interval[1]:\r\n",
    "                res += 1\r\n",
    "            elif right > interval[0] and right < interval[1]:\r\n",
    "                right = interval[1]\r\n",
    "            else:\r\n",
    "                left = interval[0]\r\n",
    "                right =  interval[1]\r\n",
    "        return len(intervals) -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\r\n",
    "        intervals.sort(key = lambda x : (x[0], -x[1]))\r\n",
    "        n = len(intervals)\r\n",
    "        mx = -1\r\n",
    "        for interval in intervals:\r\n",
    "            if interval[1] > mx:\r\n",
    "                mx = interval[1]\r\n",
    "            else:\r\n",
    "                n -= 1\r\n",
    "        return n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
